package leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.*;

public class LeetCodeMain109 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode left=lowestCommonAncestor(root.left, p, q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if (left==null&&right!=null){
            return right;
        }
        if (left!=null&&right==null){
            return left;
        }
        if (left!=null&&right!=null){
            return root;
        }
        return null;
    }
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null){
            return null;
        }
        TreeNode ans=root;
        while (true){
            if (p.val<ans.val&&ans.val>q.val){
                ans=ans.left;
            }else if (p.val>ans.val&&ans.val<q.val){
                ans=ans.right;
            }else {
                break;
            }
        }
        return ans;
    }
    public int[][] findContinuousSequence(int target) {
        List<int[]> list=new ArrayList<>();
        for (int l = 1,r=1,sum=0; r<target  ; r++) {
            sum+=r;
            while (sum>target){
                sum-=l++;
            }
            if (sum==target){
                int[] tmp=new int[r-l+1];
                for (int i = 0; i < tmp.length; i++) {
                    tmp[i]=i+l;
                }
                list.add(tmp);
            }
        }
        int[][] res = new int[list.size()][];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public String reverseLeftWords(String s, int n) {
        char[] arr=s.toCharArray();
        if (arr.length==1){
            return s;
        }
        for (int i = 0; i < n; i++) {
            char ch=arr[0];
            for (int j = 0; j < s.length()-1; j++) {
                arr[j]=arr[j+1];
            }
            arr[arr.length-1]=ch;
        }
        return String.valueOf(arr);
    }
    public int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return Math.max(left,right)+1;
    }
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int count=0;
        if (nums[0]==0){
            count++;
        }
        int sum=0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i]==0){
                count++;
                continue;
            }
            if (nums[i-1]!=0&&nums[i]==nums[i-1]){
                return false;
            }
            if (nums[i-1]!=0&&nums[i]-nums[i-1]>1){
                sum+=nums[i]-nums[i-1]-1;
            }
        }
        return count>=sum;
    }

    public int[] twoSum(int[] nums, int target) {
        int[] arr=new int[2];
        Set<Integer> set=new HashSet<>();
        for (int num:nums) {
            set.add(num);
        }
        for (int num:nums) {
            if (set.contains(target-num)){
                arr[0]=num;
                arr[1]=target-num;
            }
        }
        return arr;
    }
}
